/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-04-25
 * Time: 23:38
 */
class SinglyLinkedList {
    private ListNode head; // 链表头节点
    private int size;      // 链表长度

    /**
     * 构造方法：初始化空链表
     */
    public SinglyLinkedList() {
        head = null;
        size = 0;
    }

    // ----------------- 基本操作 -----------------

    /**
     * 在链表头部添加节点 --头插法
     * @param val 要添加的值
     */
    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val); // 创建新节点
        newNode.next = head; // 新节点指向原头节点
        head = newNode;      // 更新头节点为新节点
        size++;              // 链表长度加1
    }

    /**
     * 在链表尾部添加节点
     * @param val 要添加的值
     */
    public void addAtTail(int val) {
        if (head == null) {
            addAtHead(val); // 如果链表为空，直接头插
            return;
        }

        ListNode current = head;
        // 遍历到最后一个节点（current.next == null）
        while (current.next != null) {
            current = current.next;
        }
        current.next = new ListNode(val); // 尾部插入新节点
        size++; // 链表长度加1
    }

    /**
     * 在指定索引位置插入节点
     * @param index 插入位置（从0开始）
     * @param val 要插入的值
     */
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return; // 非法索引

        if (index == 0) {
            addAtHead(val); // 插入头部
            return;
        }

        if (index == size) {
            addAtTail(val); // 插入尾部
            return;
        }

        ListNode prev = head;
        // 找到插入位置的前一个节点（循环index-1次）
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = prev.next; // 新节点指向原位置节点
        prev.next = newNode;      // 前节点指向新节点
        size++; // 链表长度加1
    }

    /**
     * 删除指定索引位置的节点
     * @param index 要删除的位置
     */
    // 法一：按索引删除
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return; // 非法索引

        if (index == 0) {
            head = head.next; // 删除头节点
        } else {
            ListNode prev = head;
            // 找到删除位置的前一个节点（循环index-1次）
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            prev.next = prev.next.next; // 跳过被删除节点
        }
        size--; // 链表长度减1
    }

    // 删除第一次出现关键字为key的节点(按值删除）
    public void remove(int key) {
        if (head == null) return; // 空链表直接返回

        // 处理头节点为key的情况
        if (head.val == key) {
            head = head.next;
            size--; // 长度减1
            return;
        }

        ListNode prev = findKey(key); // 查找key的前驱节点
        if (prev == null) return; // 未找到key

        // 删除prev.next节点
        prev.next = prev.next.next;
        size--; // 长度减1
    }

    // 辅助方法：查找关键字为key的节点的前驱
    private ListNode findKey(int key) {
        ListNode prev = head;
        while (prev.next != null) { // 遍历链表
            if (prev.next.val == key) {
                return prev; // 找到前驱
            }
            prev = prev.next;
        }
        return null; // 未找到
    }

    // 删除所有值为key的节点
    public void removeAllKey(int key) {
        if (head == null) return;

        ListNode current = head.next;
        ListNode prev = head;

        // 遍历处理头节点之后的节点
        while (current != null) {
            if (current.val == key) {
                prev.next = current.next; // 删除current节点
                current = current.next;   // current后移
                size--; // 长度减1
            } else {
                prev = current;          // prev后移
                current = current.next; // current后移
            }
        }

        // 最后处理头节点
        if (head.val == key) {
            head = head.next;
            size--; // 长度减1
        }
    }

    // 清空链表
    public void clear() {
        // 遍历所有节点，断开引用（非必需，但更安全）
        ListNode current = head;
        while (current != null) {
            ListNode curN = current.next;
            current.next = null; // 断开当前节点的next
            current = curN;  // 移动到下一节点
        }
        head = null; // 头节点置空
        size = 0;    // 长度重置为0
    }

    /**
     * 查找节点是否存在
     * @param val 要查找的值
     * @return 是否存在
     */
    public boolean contains(int val) {
        ListNode current = head;
        while (current != null) { // 遍历链表
            if (current.val == val) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    /**
     * 获取链表长度
     * @return 当前链表长度
     */
    public int getSize() {
        return size;
    }

    /**
     * 反转链表
     * @return 反转后的链表头节点
     */
    public ListNode reverseList() {
        if (head == null) {
            return head; // 空链表直接返回
        }

        ListNode current = head.next; // 当前节点从第二个节点开始
        head.next = null;         // 原头节点变为尾节点，其 next 设为 null

        while (current != null) {     // 遍历链表直到末尾
            ListNode curN = current.next; // 保存当前节点的下一个节点
            current.next = head;      // 将当前节点插入到反转后的链表头部
            head = current;          // 更新头节点为当前节点
            current = curN;           // 移动到下一个待处理节点
        }

        return head; // 返回反转后的头节点
    }

    /**
     * 找到链表的中间节点
     * @return
     */
    public ListNode findMiddleNode() {
        if(head == null) {
            return null;
        }
        int len = getSize();
        ListNode current = head;
        int count = 0;
        while (count != len/2) {
            current = current.next;
            count++;
        }
        return current;
    }

    //法二：
    public ListNode findMiddleNode2() {
        ListNode fast = head;
        ListNode slow = head;
        //fast一定是 先走到链表尾巴的
        //while (fast.next != null && fast != null) 错的，条件不能前后换，
        // 因为比如说链表为偶数这时走到最后fast为空，fast.next也是null，会报空值异常
        while (fast != null && fast.next != null) { //这样写循环是因为当fast==null或者fast.next==null都说明fast已经遍历完了链表
            //？为什么是用&&而不是用||呢？

            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

//输入一个链表，输出该链表中倒数第k个结点。
    //法一：
    public int kthToLast( int k) {
        if(k <= 0 || k > getSize()) {
            return -1;
        }
        int len = getSize();
        int count = len-k;
        ListNode current = head;
        while (count != 0) {
            current = current.next;
            count--;
        }
        return current.val;
    }

    //法二：先让fast走k-1步，然后slow和fast一起走
    public int kthToLast2( int k) {
        if(k <= 0 ) {
            return -1;
        }
        ListNode fast = head;
        ListNode slow = head;

        int count = 0;
        while (count != k-1) {
            fast = fast.next;
            if(fast == null) {
                return -1;
            }
            count++;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }


//    //合并两个有序链表
//    public ListNode mergeTwoLists(ListNode headA,ListNode headB) {
//        ListNode newHead = new ListNode();
//        ListNode tmpH = newHead;
//        while(headA != null && headB != null) {
//            if(headA.val < headB.val) {
//                tmpH.next = headA;
//                tmpH = tmpH.next;
//                headA = headA.next;
//            }else {
//                tmpH.next = headB;
//                tmpH = tmpH.next;
//                headB = headB.next;
//            }
//        }
//        if(headA != null) {
//            tmpH.next = headA;
//        }
//
//        if(headB != null) {
//            tmpH.next = headB;
//        }
//
//        return newHead.next;
//    }



    //编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
    public ListNode partition(int x) {
        // 当前节点，从头节点开始遍历整个链表
        ListNode current = head;

        // 小值链表的头节点和尾节点（存储所有值小于x的节点）
        ListNode smallHead = null;
        ListNode smallTail = null;
        // 大值链表的头节点和尾节点（存储所有值大于等于x的节点）
        ListNode largeHead = null;
        ListNode largeTail = null;

        // 遍历原链表，将节点按值分配到小链表或大链表
        while (current != null) {
            if (current.val < x) {
                // 当前节点值小于x，加入小链表
                if (smallHead == null) {
                    // 小链表为空时，头尾均指向当前节点（首次插入）
                    smallHead = smallTail = current;
                } else {
                    // 小链表不为空，将当前节点追加到尾节点后，并更新尾节点
                    smallTail.next = current;
                    smallTail = smallTail.next;
                }
            } else {
                // 当前节点值大于等于x，加入大链表
                if (largeHead == null) {
                    // 大链表为空时，头尾均指向当前节点（首次插入）
                    largeHead = largeTail = current;
                } else {
                    // 大链表不为空，将当前节点追加到尾节点后，并更新尾节点
                    largeTail.next = current;
                    largeTail = largeTail.next;
                }
            }
            // 移动到原链表的下一个节点
            current = current.next;
        }


        //以下是合并链表

        // 若小链表为空的情况（所有节点均在大链表中）
        if (smallHead == null) {
            return largeHead;  // 直接返回大链表的头节点
        }

        // 否则连接小链表和大链表
        smallTail.next = largeHead;  // 小链表的尾部指向大链表的头部

        // 关键细节：若大链表非空，需确保其尾节点的next为null，防止链表成环
        if (largeHead != null) {
            largeTail.next = null;
        }

        // 返回合并后的链表头节点（小链表的头节点）
        return smallHead;
    }
    /**
     * 打印链表内容
     */
    public void printList() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}